package com.chj.chuji.tijie04;

//https://blog.csdn.net/qq_23523409/article/details/84260358?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param
public class ListNodeTet {
	public static class ListNode {
		int val;
		ListNode next = null;

		ListNode(int x) {
			val = x;
		}
	}

	public static ListNode insertionSortList(ListNode head) {
		// write code here
		ListNode res = new ListNode(0);// 创建新节点用来排序
		ListNode pre = res;
		ListNode current = head;
		while (current != null) {

			System.out.println("===222");
			printCircularList("res", res);
			printCircularList("cur", current);
			printCircularList("pre", pre);
			System.out.println("===222");
			// 找到需要插入的位置
			pre = res;
			while (pre.next != null && pre.next.val < current.val) {
				pre = pre.next;
			}
			// 进行节点的插入
			ListNode tmp = current.next;
			current.next = pre.next;
			pre.next = current;
			current = tmp;

			System.out.println("===111");
			printCircularList("res", res);
			printCircularList("tmp", tmp);
			printCircularList("cur", current);
			printCircularList("pre", pre);
			System.out.println("===111");
			System.out.println();
		}
		return res.next;
	}

	public static void printCircularList(String str, ListNode head) {
		if (head == null) {
			return;
		}
		System.out.print(str + " List: " + head.val + " ");
		ListNode cur = head.next;
		while (cur != head && cur != null) {
			System.out.print(cur.val + " ");
			cur = cur.next;
		}
		System.out.println("|| header-> " + head.val);
	}

	public static void main(String[] args) {
		ListNode head2 = new ListNode(4);
		head2.next = new ListNode(2);
		head2.next.next = new ListNode(1);
		head2.next.next.next = new ListNode(3);
		printCircularList("test", head2);
		ListNode head4 = insertionSortList(head2);
		printCircularList("test", head4);

		ListNode head3 = new ListNode(-1);
		head3.next = new ListNode(5);
		head3.next.next = new ListNode(3);
		head3.next.next.next = new ListNode(4);
		head3.next.next.next.next = new ListNode(0);
		printCircularList("test", head3);
		ListNode head5 = insertionSortList(head3);
		printCircularList("test", head5);
	}
}
